P2891 [USACO07OPEN]Dining G 题解
难度：⭐⭐⭐⭐
知识点：最大流
题目链接
序言：
我太难了QwQ，紫题啊！OI第一紫，达成！
1. 入手程序
新学习的最大流试一下啊
后来发现做得第二题就做这题是真心累
2. 编程思路
首先，假设你知道怎么做最大流（我会写滴，敬请期待~）
那我们现在需要的就是把这题的数据转化为最大流的模型。
下面请看图~
建一个超级源点S，一个超级汇点T，其他值按图上建边，权值都为1
有人问：
牛为什么分为入点和出点啊？
如果不分的话，那么就会无法解决一个重大的问题：
一头牛可能占用多个食物或饮料！！！
3. AC代码
#include<bits/stdc++.h>
using namespace std;
int e[501][501], book[501], s[501], top = 0, n, f,d, flag, ans,z;
void dfs(int u)
{
if (book[u] == 1)
return;
book[u] = 1;
top++;
s[top] = u;
if (u == z)
{
int minv = 999999999;
for (int i = 1; i <= top - 1; i++)
{
//cout << s[i] << " ";
if (minv > e[s[i]][s[i + 1]])
minv = e[s[i]][s[i + 1]];
}
if (minv != 999999999)
{
flag = 1;
for (int i = 1; i <= top - 1; i++)
{
e[s[i]][s[i + 1]] -= minv;
e[s[i + 1]][s[i]] += minv;//在反向边上加上减去的流量
}
ans += minv;//累加所有的流量
}
top--;
return;
}
for (int i = 1; i <= z; i++)
{
if (e[u][i] > 0)
{
dfs(i);
}
}
top--;
return;
}
int main()
{
/*
4 3 3
2 2 1 2 3 1
2 2 2 3 1 2
2 2 1 3 1 2
2 1 1 3 3
*/
cin >> n >> f >> d;
for (int i = 1; i <= n; i++)
{
int t1,t2,t;
cin >> t1 >> t2;
for(int j=1;j<=t1;j++)
{
cin >> t;
e[t][f+i]=1;
}
for(int j=1;j<=t2;j++)
{
cin >> t;
e[f+n+i][f+2*n+t]=1;
}
}
//源点
for(int i=1;i<=f;i++)
{
e[0][i]=1;
}
//汇点
z=f+2*n+d+1;
for(int i=f+2*n+1;i<=f+2*n+d;i++)
{
e[i][f+2*n+d+1]=1;
}
//
for(int i=f+1; i<=f+n;i++)
{
e[i][i+n]=1;
}
/*
for(int i=0;i<=z;i++)
{
for(int j=0;j<=z;j++)
{
if(e[i][j]==1)
{
cout << i << " " <<j << endl;
}
}
}
*/
while (1 > 0)
{
memset(book, 0, sizeof(book));
flag = 0;
dfs(0);
if (flag == 0)
break;
}
cout << ans;
return 0;
}
/*
0 1
0 2
0 3
1 4
1 6
1 7
2 4
2 5
3 5
3 6
3 7
4 8
5 9
6 10
7 11
8 12
8 14
9 12
9 13
10 12
10 13
11 14
12 15
13 15
14 15
*/
